7、全球变暖

题目 全球变暖

image-422f1f5f

思路分析

模拟

dfs统计涨水前的岛屿数量

进行涨水操作（注意不要对每个都进行操作 而是记录下来最后统一操作 避免涨了 又涨的情况 即状态被前面的操作改变 最后可能导致全被淹没）

然后再统计一遍涨水后的岛屿数量

相减就是答案

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N = 1010;
string s[N];
bool visited[N][N];
int n;

void dfs(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= n || s[x][y] == '.' || visited[x][y]) return;
    visited[x][y] = true;
    dfs(x-1, y); // 上
    dfs(x+1, y); // 下
    dfs(x, y-1); // 左
    dfs(x, y+1); // 右
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> s[i];

//	cout<<endl;

    int old_blocks = 0;
    memset(visited, false, sizeof visited);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
//        	cout<<s[i][j];
            if (s[i][j] == '#' && !visited[i][j]) {
                dfs(i, j);
                old_blocks++;
            }
        }
//        cout<<endl;
    }
//    cout<<endl;
//    cout<<"old_blocks: "<<old_blocks<<endl;

	vector<PII> to_change;
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
	        if (s[i][j] == '.') {
	            if (i > 0)
	            	to_change.push_back({i - 1, j});
	            if (j < n - 1)
					 to_change.push_back({i, j + 1});
	            if (i < n - 1)
	            	to_change.push_back({i + 1, j});
	            if (j > 0)
				 	to_change.push_back({i, j - 1});
	        }
	    }
	}
	for(auto idx:to_change){
		int x=idx.first,y=idx.second;
		s[x][y]='.';
	}

	int new_blocks = 0;
    memset(visited, false, sizeof visited);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
//        	cout<<s[i][j];
            if (s[i][j] == '#' && !visited[i][j]) {
                dfs(i, j);
                new_blocks++;
            }
        }
//        cout<<endl;
    }
//    cout<<endl;
//    cout<<"new_blocks: "<<new_blocks<<endl;

    cout<<old_blocks-new_blocks;
    return 0;
}

过了三个数据 7分

image-e5478f3a

这样写其实是错的

image-8ee4ee58

对比这个数据就可以得知

问的是被淹没的岛屿数有多少个

而模拟涨水 虽然能成功把淹没的岛屿处理掉 但是 在淹没某些岛屿后 又会出现新的岛屿

最后把新岛屿数减去旧岛屿数 并不是被淹没的岛屿的数量

所以核心是 不能去改变岛屿的状态 只能找到一定不会被淹没的岛屿数量 去与原岛屿数量相减

或者直接找被淹没的岛屿数

首先洪水灌溉可以求出连通块的总数量

如果某个连通块不会被全淹没 就说明连通块里有一个点的周围都是#

那么就可以传入一个参数 标记某个连通块是否可以存活 根据标记记录存活的连通块的数量

用总数量减去存活的数量 就是消失的数量

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=1010;
char g[N][N];
bool st[N][N];
int n;
int all,cnt;

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
	return x>=0 && x<=n-1 && y>=0 && y<=n-1;
}
void dfs(int x,int y,bool &live){
    //不知道为什么 剪枝会错 哦知道了 提前退出会导致岛没被拓展完全 使得没被标记
    //if(live==true)    return;

    //只要找到一个4周都不是水的 就说明整个岛不会完全消失
	if(live==false){
		int cntland=0;
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(g[nx][ny]!='.')
				cntland++;
		}
		if(cntland==4)
			live=true;
	}

	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(isVaild(nx,ny) && g[nx][ny]=='#' && !st[nx][ny]){
			st[nx][ny]=true;
			dfs(nx,ny,live);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>g[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(g[i][j]=='#' && !st[i][j]){
				bool live=false;
				st[i][j]=true;
				dfs(i,j,live);
				all++;
				if(live)
					cnt++;
			}
		}
	}
	cout<<all-cnt<<endl;
	return 0;
}

同类题型

视频讲解

⬅️ DFS 🏠 00-刷题理模型 ➡️ Flood Fill 连通块